package com.leetcode.BinaryTree;

import java.util.HashMap;

//从前序与中序遍历序列构造二叉树
public class lc_105 {
    public static void main(String[] args) {

    }

    // 用于存储前序遍历数组
    int[] preorder;
    // 哈希表，用于存储中序遍历数组中每个元素及其对应的索引
    HashMap<Integer, Integer> dic = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // 遍历中序遍历数组，将元素及其索引存入哈希表
        for(int i = 0; i < inorder.length; i++){
            dic.put(inorder[i], i);
        }
        // 调用递归方法，从根节点开始构建二叉树
        return recur(0, 0, inorder.length - 1);
    }

    /**
     * 辅助递归方法，用于递归构建二叉树
     * 1. 判断是否新建新方法：需要,因为传入传出参数原方法满足不了
     * 2. 传入传出参数：
     *    - 传入参数：
     *      - root：前序遍历数组中当前根节点的索引
     *      - left：中序遍历数组中当前子树的左边界索引
     *      - right：中序遍历数组中当前子树的右边界索引
     *    - 传出参数：返回当前子树的根节点
     * 3. 递归终止条件：
     *    - 当 left > right 时，说明当前子树为空，返回 null
     * 4. 每一层逻辑：
     *    - 根据前序遍历数组中当前根节点的索引 root 获取根节点的值，创建根节点
     *    - 通过哈希表 dic 查找当前根节点在中序遍历数组中的索引 i
     *    - 递归构建左子树：左子树的根节点在前序遍历数组中的索引为 root + 1，左子树在中序遍历数组中的范围是 [left, i - 1]
     *    - 递归构建右子树：右子树的根节点在前序遍历数组中的索引为 root + i - left + 1，右子树在中序遍历数组中的范围是 [i + 1, right]
     *    - 返回当前子树的根节点
     */
    private TreeNode recur(int root, int left, int right) {
        // 递归终止条件：如果左边界大于右边界，说明当前子树为空，返回 null
        if(left > right){
            return null;
        }
        // 根据前序遍历数组中当前根节点的索引创建根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 通过哈希表查找当前根节点在中序遍历数组中的索引
        int i = dic.get(preorder[root]);
        // 递归构建左子树
        node.left = recur(root + 1, left, i - 1);
        // 递归构建右子树
        node.right = recur(root + i - left + 1, i + 1, right);
        // 返回当前子树的根节点
        return node;
    }
}
